#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>

#include "common/utils.hpp"

/*
二叉搜索树中，中序遍历遇到的第一个值在p、q节点值之间的节点就是 最近公共祖先

*/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while(root != nullptr) {
        if (root->val > p->val && root->val > q->val) {
            root = root->left;
        } else if (root->val < p->val && root->val < q->val) {
            root = root->right;
        } else {
            return root;
        }
    }

    return nullptr;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> nums = {2, 1};
    TreeNode* node = createTreeNodeByArray(nums);
    printTreeNode(node);
    std::cout << "=================\n";
    TreeNode* ret = lowestCommonAncestor(node, node, node->left);
    printTreeNode(ret);
}